{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest K LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #quickselect #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #快速选择 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小K个数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> arr = [1,3,5,7,2,4,6,8], k = 4\n",
    "<strong>输出：</strong> [1,2,3,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= len(arr) &lt;= 100000</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= min(100000, len(arr))</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-k-lcci](https://leetcode.cn/problems/smallest-k-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-k-lcci](https://leetcode.cn/problems/smallest-k-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        heapq.heapify(arr)\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heapq.heappop(arr))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        heapq.heapify(arr)\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heapq.heappop(arr))\n",
    "        return res\n",
    "        # return heapq.nsmallest(k,arr)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        heapify(arr)\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(heappop(arr))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        heapq.heapify(arr)\n",
    "        return [heapq.heappop(arr) for _ in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        import heapq\n",
    "        heapq.heapify(arr)\n",
    "        for _ in range(k):\n",
    "            res.append(heapq.heappop(arr))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        # def quicksort(left, right):\n",
    "        #     if left >= right: return\n",
    "        #     pivot = arr[left]\n",
    "        #     i, j = left, right\n",
    "        #     while i < j:\n",
    "        #         while i < j and arr[j] > pivot:\n",
    "        #             j -= 1\n",
    "        #         arr[i] = arr[j]\n",
    "        #         while i < j and arr[i] <= pivot:\n",
    "        #             i += 1\n",
    "        #         arr[j] = arr[i]\n",
    "        #     arr[i] = pivot\n",
    "        #     if i == k - 1:\n",
    "        #         return\n",
    "        #     elif i < k - 1:\n",
    "        #         quicksort(i+1, right)\n",
    "        #     else:\n",
    "        #         quicksort(left, i-1)\n",
    "        # quicksort(0, len(arr)-1)\n",
    "        # return arr[:k]\n",
    "\n",
    "\n",
    "\n",
    "        # if k == 0:\n",
    "        #     return []\n",
    "        # hp = [-x for x in arr[:k]]\n",
    "        # heapq.heapify(hp)\n",
    "        # for i in range(k, len(arr)):\n",
    "        #     if -hp[0] > arr[i]:\n",
    "        #         heapq.heappop(hp)\n",
    "        #         heapq.heappush(hp, -arr[i])\n",
    "        # ans = [-x for x in hp]\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "        heapq.heapify(arr)\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heapq.heappop(arr))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        arr.sort()\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(arr[i])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        return arr[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def sift(li, low, high):\n",
    "            i = low\n",
    "            j = 2 * i + 1\n",
    "            tmp = li[low]\n",
    "            while j <= high:\n",
    "                if j + 1 <= high and li[j + 1] > li[j]:\n",
    "                    j = j + 1\n",
    "                if li[j] > tmp:\n",
    "                    li[i] = li[j]\n",
    "                    i = j\n",
    "                    j = 2 * i + 1\n",
    "                else:\n",
    "                    li[i] = tmp\n",
    "                    break\n",
    "            else:\n",
    "                li[i] = tmp\n",
    "        \n",
    "        for i in range((k - 2) // 2, -1, -1):\n",
    "            sift(arr, i, k - 1)\n",
    "        for i in range(k, len(arr)):\n",
    "            if arr[i] < arr[0]:\n",
    "                arr[i], arr[0] = arr[0], arr[i]\n",
    "                sift(arr, 0, k - 1)\n",
    "        for i in range(k - 1, -1, -1):\n",
    "            arr[i], arr[0] = arr[0], arr[i]\n",
    "            sift(arr, 0, i - 1)\n",
    "        \n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        return sorted(arr)[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        # 第k小的数的索引是k-1，当k为0时，直接返回空列表\n",
    "        if k == 0:\n",
    "            return []\n",
    "        \n",
    "        # import random\n",
    "        def quickSort(l: int, r: int) -> int:\n",
    "            # randIdx = random.randint(l, r)\n",
    "            # arr[l], arr[randIdx] = arr[randIdx], arr[l]\n",
    "\n",
    "            pivot = arr[l]\n",
    "            lIdx = l\n",
    "            rIdx = r\n",
    "            while lIdx < rIdx:\n",
    "                while lIdx < rIdx and arr[rIdx] >= pivot:\n",
    "                    rIdx -= 1\n",
    "                if lIdx < rIdx and arr[rIdx] < pivot:\n",
    "                    arr[lIdx] = arr[rIdx]\n",
    "\n",
    "                while lIdx < rIdx and arr[lIdx] <= pivot:\n",
    "                    lIdx += 1\n",
    "                if lIdx < rIdx and arr[lIdx] > pivot:\n",
    "                    arr[rIdx] = arr[lIdx]\n",
    "            arr[lIdx] = pivot\n",
    "            return lIdx\n",
    "        \n",
    "        l, r = 0, len(arr) - 1\n",
    "        pivotIdx = quickSort(l, r)\n",
    "        while pivotIdx != k-1:\n",
    "            if pivotIdx < k-1:\n",
    "                l = pivotIdx + 1\n",
    "                pivotIdx = quickSort(l, r)\n",
    "            else:\n",
    "                r = pivotIdx - 1\n",
    "                pivotIdx = quickSort(l, r)\n",
    "        \n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def heap_sort(nums, start, end):\n",
    "            root = start\n",
    "            while 2 * root + 1 <= end:\n",
    "                if 2 * root + 2 <= end and nums[2 * root + 2] < nums[2 * root + 1]:\n",
    "                    idx = 2 * root + 2\n",
    "                else:\n",
    "                    idx = 2 * root + 1\n",
    "                if nums[root] > nums[idx]:\n",
    "                    nums[root], nums[idx] = nums[idx], nums[root]\n",
    "                    root = idx\n",
    "                else:\n",
    "                    break\n",
    "            return nums\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            arr = heap_sort(arr, i, len(arr) - 1)\n",
    "        for i in range(k):\n",
    "            arr[0], arr[len(arr)-1-i] = arr[len(arr)-1-i], arr[0]\n",
    "            arr = heap_sort(arr, 0, len(arr) - 2 - i)\n",
    "        return arr[len(arr)-k : ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        import heapq\n",
    "        heap = []\n",
    "        for i in arr:\n",
    "            heapq.heappush(heap, i)\n",
    "        res = []\n",
    "        for _ in range(k):\n",
    "            res.append(heapq.heappop(heap))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        q = [i for i in arr] \n",
    "        heapify(q)\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(heapq.heappop(q))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def quick_sort(self, nums, l, r):\n",
    "        p = nums[r]\n",
    "        i = l - 1\n",
    "        for j in range(l, r):\n",
    "            if nums[j] <= p:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "    \n",
    "    def random_pos(self, nums, l, r):\n",
    "        i = random.randint(l, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return self.quick_sort(nums, l, r)\n",
    "\n",
    "    def select(self, arr, l, r, k):\n",
    "        p = self.random_pos(arr, l, r)\n",
    "        num = p - l + 1\n",
    "        if k < num:\n",
    "            self.select(arr, l, p - 1, k)\n",
    "        elif k > num:\n",
    "            self.select(arr, p + 1, r, k - num)\n",
    "\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:\n",
    "            return []\n",
    "        self.select(arr, 0, len(arr) - 1, k)\n",
    "        return arr[: k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def partition(self, nums, p, r):\n",
    "        pivot = nums[r]\n",
    "        i = p - 1\n",
    "        for j in range(p, r):\n",
    "            if nums[j] <= pivot:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "        nums[i + 1], nums[r] = nums[r], nums[i + 1]\n",
    "        return i + 1\n",
    "\n",
    "    def randomized_partition(self, nums, p, r):\n",
    "        i = random.randint(p, r)\n",
    "        nums[r], nums[i] = nums[i], nums[r]\n",
    "        return self.partition(nums, p, r)\n",
    "\n",
    "    def quicksort(self,nums,p,r,k):\n",
    "        q = self.randomized_partition(nums,p,r)\n",
    "        l = q - p + 1\n",
    "        if k > l:\n",
    "            self.quicksort(nums,q+1,r,k-l)\n",
    "        elif k<l:\n",
    "            self.quicksort(nums,p,q-1,k)\n",
    "\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:\n",
    "            return []\n",
    "        self.quicksort(arr,0,len(arr)-1,k)\n",
    "        return arr[:k] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        heap = []\n",
    "        for num in arr:\n",
    "            heapq.heappush(heap, num)   \n",
    "        heap_sort=[heapq.heappop(heap) for _ in range(len(heap))]\n",
    "        return heap_sort[0:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        self.sort(arr, 0, len(arr)-1, k)\n",
    "        return arr[:k]\n",
    "\n",
    "    def sort(self, nums, left, right,k):\n",
    "        if left >= right: return \n",
    "        \n",
    "        j = self.partition(nums, left, right)\n",
    "\n",
    "        if j < k:  self.sort(nums, j+1, right, k)\n",
    "        elif j > k: self.sort(nums, left, j-1, k)\n",
    "        else: return\n",
    "    \n",
    "    def partition(self, nums, left, right):\n",
    "        pivot = nums[right]\n",
    "        less = left\n",
    "        great = left\n",
    "        while great <= right:\n",
    "            if nums[great] < pivot:\n",
    "                nums[great],nums[less] = nums[less],nums[great]\n",
    "                less+=1\n",
    "            great +=1\n",
    "        nums[less],nums[right] = nums[right],nums[less]\n",
    "        return less\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def quick_sort(li, start, end, k):\n",
    "            if start >= end:\n",
    "                return li[start]\n",
    "            i = randomized_partition(li, start, end)\n",
    "            if i == k:\n",
    "                return li[i]\n",
    "            elif i > k:\n",
    "                return quick_sort(li, start, i - 1, k)\n",
    "            else:\n",
    "                return quick_sort(li, i + 1, end, k)\n",
    "\n",
    "        def randomized_partition(li, start, end):\n",
    "            n = random.randint(start, end)\n",
    "            li[end], li[n] = li[n], li[end]\n",
    "            return partition(li, start, end)\n",
    "\n",
    "        def partition(li, start, end):\n",
    "            i = start - 1\n",
    "            for j in range(start, end):\n",
    "                if li[j] < li[end]:\n",
    "                    i += 1\n",
    "                    li[i], li[j] = li[j], li[i]\n",
    "            i += 1\n",
    "            li[i], li[end] = li[end], li[i]\n",
    "            return i\n",
    "        if not arr:\n",
    "            return []\n",
    "        quick_sort(arr, 0, len(arr) - 1, k)\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def quick_s(arr,k,start,end):\n",
    "            l,r = start,end\n",
    "            mid = arr[start]\n",
    "            while l < r:\n",
    "                while l < r and arr[r]>= mid:\n",
    "                    r -= 1\n",
    "                arr[l] = arr[r]\n",
    "                while l < r and arr[l] < mid:\n",
    "                    l += 1\n",
    "                arr[r] = arr[l]\n",
    "            arr[l] = mid\n",
    "            if l+1 == k:\n",
    "                return arr[:l+1]\n",
    "            if l+1 > k:\n",
    "                return quick_s(arr,k,start,l-1)\n",
    "            elif l+1 < k:\n",
    "                return quick_s(arr,k,l+1,end)\n",
    "        if k == 0:\n",
    "            return []\n",
    "        return quick_s(arr,k,0,len(arr)-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def quick_sort(li, start, end, k):\n",
    "            if start >= end:\n",
    "                return li[start]\n",
    "            i = randomized_partition(li, start, end)\n",
    "            if i == k:\n",
    "                return li[i]\n",
    "            elif i > k:\n",
    "                return quick_sort(li, start, i - 1, k)\n",
    "            else:\n",
    "                return  quick_sort(li, i + 1, end, k)\n",
    "\n",
    "        def randomized_partition(li, start, end):\n",
    "            n = random.randint(start, end)\n",
    "            li[end], li[n] = li[n], li[end]\n",
    "            return partition(li, start, end)\n",
    "\n",
    "        def partition(li, start, end):\n",
    "            i = start - 1\n",
    "            for j in range(start, end):\n",
    "                if li[j] < li[end]:\n",
    "                    i += 1\n",
    "                    li[i], li[j] = li[j], li[i]\n",
    "            i += 1\n",
    "            li[i], li[end] = li[end], li[i]\n",
    "            return i\n",
    "        if not arr:\n",
    "            return []\n",
    "        quick_sort(arr, 0, len(arr) - 1, k)\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        self.mergeSort(arr, 0, len(arr)-1)\n",
    "        return arr[:k]\n",
    "    \n",
    "    def mergeSort(self, arr, start, end):\n",
    "        \"\"\" 通过递归对左右两边元素进行归并排序 \"\"\"\n",
    "        if start < end:\n",
    "            mid = int((start+end)/2)\n",
    "            self.mergeSort(arr, start, mid)  # 对左半边的元素进行排序\n",
    "            self.mergeSort(arr, mid+1, end)  # 对右半边的元素进行排序\n",
    "            self.mergeArray(arr, start, mid, end)  # 待左右两边元素有序后，进行合并操作\n",
    "\n",
    "    def mergeArray(self, arr, start, mid, end):\n",
    "        \"\"\" 将有序数组arr[start ~ mid]和arr[mid+1 ~ end]合并 \"\"\"\n",
    "        tmp = []  # 辅助数组，用于暂时存储排序后的元素\n",
    "        p1, p2 = start, mid+1  # 双指针：p1指向左半边的元素，p2指向右半边的元素\n",
    "        while p1 <= mid and p2 <= end:  # 寻找较小的元素\n",
    "            if arr[p1] < arr[p2]:\n",
    "                tmp.append(arr[p1])\n",
    "                p1 += 1\n",
    "            else:\n",
    "                tmp.append(arr[p2])\n",
    "                p2 += 1\n",
    "        if p1 <= mid:  # 若左半边还有剩余元素，将其直接添至辅助数组中\n",
    "            tmp.extend(arr[p1:mid+1])\n",
    "        elif p2 <= end:  # 若右半边还有剩余元素，将其直接添至辅助数组中\n",
    "            tmp.extend(arr[p2:end+1])\n",
    "        arr[start:end+1] = tmp  # 将排序后的辅助数组赋值给原数组\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def quicksort(left, right):\n",
    "            if left >= right: return\n",
    "            pivot = arr[left]\n",
    "            i, j = left, right\n",
    "            while i < j:\n",
    "                while i < j and arr[j] > pivot:\n",
    "                    j -= 1\n",
    "                arr[i] = arr[j]\n",
    "                while i < j and arr[i] <= pivot:\n",
    "                    i += 1\n",
    "                arr[j] = arr[i]\n",
    "            arr[i] = pivot\n",
    "            if i == k - 1:\n",
    "                return\n",
    "            elif i < k - 1:\n",
    "                quicksort(i+1, right)\n",
    "            else:\n",
    "                quicksort(left, i-1)\n",
    "        quicksort(0, len(arr)-1)\n",
    "        return arr[:k]\n",
    "\n",
    "\n",
    "\n",
    "        # if k == 0:\n",
    "        #     return []\n",
    "        # hp = [-x for x in arr[:k]]\n",
    "        # heapq.heapify(hp)\n",
    "        # for i in range(k, len(arr)):\n",
    "        #     if -hp[0] > arr[i]:\n",
    "        #         heapq.heappop(hp)\n",
    "        #         heapq.heappush(hp, -arr[i])\n",
    "        # ans = [-x for x in hp]\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n",
    "        # heapq.heapify(arr)\n",
    "        # res = []\n",
    "        # for i in range(k):\n",
    "        #     res.append(heapq.heappop(arr))\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, nums: List[int], k: int) -> List[int]: \n",
    "        if k == 0:\n",
    "            return []\n",
    "        import random\n",
    "        def mysort(l, r):\n",
    "            pivot_idx = random.randint(l, r)\n",
    "            pivot = nums[pivot_idx]\n",
    "            nums[r], nums[pivot_idx] = nums[pivot_idx], nums[r] \n",
    "            less_equal = l - 1 \n",
    "            for i in range(l, r+1):\n",
    "                if nums[i] <= pivot:\n",
    "                    less_equal += 1\n",
    "                    nums[i], nums[less_equal] = nums[less_equal], nums[i]\n",
    "            \n",
    "            if k - 1 == less_equal:\n",
    "                return nums[0: less_equal+1]\n",
    "            elif k - 1 < less_equal:\n",
    "                return mysort(l, less_equal-1)\n",
    "            else:\n",
    "                return mysort(less_equal-1, r)\n",
    "        return mysort(0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:return []\n",
    "        n = len(arr)\n",
    "        import random\n",
    "        def partition(l, r):\n",
    "            if l >= r: return\n",
    "            idx = random.randint(l, r)\n",
    "            arr[l], arr[idx] = arr[idx], arr[l]\n",
    "            p = l\n",
    "            p2 = r\n",
    "            while l < r:\n",
    "                while arr[r] > arr[p] and l < r:\n",
    "                    r -= 1\n",
    "                while arr[l] <= arr[p] and l < r:\n",
    "                    l += 1\n",
    "                if l < r: arr[l], arr[r] = arr[r], arr[l]\n",
    "            if l == r:\n",
    "                arr[p], arr[l] = arr[l], arr[p]\n",
    "            if k > l:\n",
    "                partition(l + 1, p2)\n",
    "            elif k < l:\n",
    "                partition(p, l - 1)\n",
    "        \n",
    "        partition(0, n - 1)\n",
    "        return arr[:k]\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k==0:return []\n",
    "        res = SortedList()\n",
    "        for c in arr:\n",
    "            if len(res)<k:\n",
    "                res.add(c)\n",
    "            else:\n",
    "                if res[-1]>c:\n",
    "                    res.pop()\n",
    "                    res.add(c)\n",
    "        return list(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def quickSort(self, arr, left, right):\n",
    "        if left < right:\n",
    "            # mid = left + (right - left) // 2\n",
    "            mid = self.sort(arr, left, right)\n",
    "            self.quickSort(arr, left, mid - 1)\n",
    "            self.quickSort(arr, mid + 1, right)\n",
    "\n",
    "    def sort(self, nums, left, right):\n",
    "        pivot = nums[left]\n",
    "        while left < right:\n",
    "            while left < right and nums[right] >= pivot:\n",
    "                right -= 1\n",
    "            nums[left] = nums[right]\n",
    "            while left < right and nums[left] <= pivot:\n",
    "                left += 1\n",
    "            nums[right] = nums[left]\n",
    "        nums[left] = pivot\n",
    "        return left\n",
    "\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        self.quickSort(arr, 0, len(arr) - 1)\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def get_partition(lists, l, r):\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while i<j and lists[j] >= lists[l]: j-=1\n",
    "                while i<j and lists[i] <= lists[l]: i+=1\n",
    "                lists[i], lists[j] = lists[j], lists[i]\n",
    "            lists[l], lists[i] = lists[i], lists[l]\n",
    "            return i\n",
    "\n",
    "        def quick_sort(lists, l, r):\n",
    "            if l >= r: return []\n",
    "            i = get_partition(lists, l, r)\n",
    "            quick_sort(lists, l, i-1)\n",
    "            quick_sort(lists, i+1, r)\n",
    "\n",
    "        quick_sort(arr, 0, len(arr)-1)\n",
    "        # print(arr)\n",
    "        return arr[:k]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def get_partition(lists, l, r):\n",
    "            i, j = l, r\n",
    "            while i < j:\n",
    "                while i<j and lists[j] >= lists[l]: j-=1\n",
    "                while i<j and lists[i] <= lists[l]: i+=1\n",
    "                lists[i], lists[j] = lists[j], lists[i]\n",
    "            lists[l], lists[i] = lists[i], lists[l]\n",
    "            return i\n",
    "\n",
    "        def quick_sort_k(lists, l, r):\n",
    "            if l >= r: return []\n",
    "            i = get_partition(lists, l, r)\n",
    "            quick_sort_k(lists, l, i-1)\n",
    "            quick_sort_k(lists, i+1, r)\n",
    "\n",
    "        quick_sort_k(arr, 0, len(arr)-1)\n",
    "        # print(arr)\n",
    "        return arr[:k]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def sort(arry, l, r):\n",
    "            if l>=r: return\n",
    "            i, j = l, r\n",
    "            while i<j:\n",
    "                while i<j and arry[j]>=arry[l]: \n",
    "                    j -= 1\n",
    "                while i< j and arry[i]<=arry[l]:\n",
    "                    i +=1\n",
    "                arry[i], arry[j] = arry[j], arry[i]\n",
    "            arry[i], arry[l] = arry[l], arry[i]\n",
    "            sort(arry, l , i-1)\n",
    "            sort(arry, i+1, r)\n",
    "        sort(arr, 0, len(arr)-1)\n",
    "        # print(tinput)\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        res=[]\n",
    "        for n in arr:\n",
    "            hq.heappush(res,-n)\n",
    "            if len(res)>k:\n",
    "                hq.heappop(res)\n",
    "        for i in range(len(res)):\n",
    "            res[i]*=-1\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1,2,3]\n",
    "0\n",
    "[1,3,5,7,2,4,6,8]\n",
    "4\n",
    "[]\n",
    "0\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        heap = []\n",
    "        for x in arr:\n",
    "            heapq.heappush(heap, -x)\n",
    "            if len(heap) > k:\n",
    "                heapq.heappop(heap)\n",
    "        res = []\n",
    "        while heap:\n",
    "            res.append(-heapq.heappop(heap))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if not k:\n",
    "            return []\n",
    "        if len(arr) <= k:\n",
    "            return arr\n",
    "        leftK = self.smallestK(arr[:len(arr) // 2], k)\n",
    "        rightK = self.smallestK(arr[len(arr) // 2:], k)\n",
    "        twoK = leftK + rightK\n",
    "        return sorted(twoK)[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        self.quickSort(arr, 0, len(arr) - 1)\n",
    "        return arr[:k]\n",
    "    def quickSort(self, arr, start, end):\n",
    "        if start < end:\n",
    "            pivot = arr[start]\n",
    "            i , j = start, end #双指针\n",
    "            while i < j:\n",
    "                while i < j and arr[j] >= pivot:\n",
    "                    j -= 1\n",
    "                if i < j :\n",
    "                    arr[i] = arr[j]\n",
    "                    i += 1\n",
    "                while i < j and arr[i] <= pivot:\n",
    "                    i += 1\n",
    "                if i < j:\n",
    "                    arr[j] = arr[i]\n",
    "                    j -= 1\n",
    "            arr[i] = pivot\n",
    "            self.quickSort(arr, start, i-1)\n",
    "            self.quickSort(arr, i+1, end)\n",
    "\n",
    "            # 6\n",
    "            # 6 1 2 7 9 3 4 5 10\n",
    "            # i             j  \n",
    "            # 5 1 2 4 3 6 9 7 10\n",
    "            #         i   j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        l = SortedList()\n",
    "        res = []\n",
    "        if k == 0:\n",
    "            return []\n",
    "        for num in arr:\n",
    "            l.add(num)\n",
    "        return list(l)[:k]\n",
    "\n",
    "        #最大堆\n",
    "        # hp = []\n",
    "        # ans = []\n",
    "        # n = len(arr)\n",
    "        # for x in arr:\n",
    "        #     heapq.heappush(hp,x)\n",
    "        #     while len(hp) > n-k:\n",
    "        #         ans.append(heapq.heappop(hp))\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k > len(arr) or k == 0 :return []\n",
    "        heap = []\n",
    "        for i in arr[:k]:\n",
    "            heapq.heappush(heap,-i)\n",
    "\n",
    "        for i in arr[k:]:\n",
    "            if i < - heap[0]:\n",
    "                heapq.heappop(heap)\n",
    "                heapq.heappush(heap,-i)\n",
    "\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(-heapq.heappop(heap))\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        return nsmallest(k,arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        if k == 0:\n",
    "            return []\n",
    "\n",
    "        def partition(arr, left, right):\n",
    "            idx = random.randint(left, right)\n",
    "            arr[left], arr[idx] = arr[idx], arr[left]\n",
    "            pivot = arr[left]\n",
    "            i, j = left, right\n",
    "            while i < j:\n",
    "                while i < j and arr[j] >= pivot: j -= 1\n",
    "                if i < j: arr[i] = arr[j]\n",
    "                while i < j and arr[i] <= pivot: i += 1\n",
    "                if i < j: arr[j] = arr[i]\n",
    "            arr[i] = pivot\n",
    "            return i\n",
    "\n",
    "        def top_k(arr, left, right):\n",
    "            if left >= right:\n",
    "                return \n",
    "            idx = partition(arr, left, right)\n",
    "            # if idx == k - 1:\n",
    "            #     return\n",
    "            if idx < k - 1:\n",
    "                top_k(arr, left, idx - 1)\n",
    "                top_k(arr, idx + 1, right)\n",
    "            else:\n",
    "                top_k(arr, left, idx - 1)\n",
    "        top_k(arr, 0, n - 1)\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        return heapq.nsmallest(k, arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def quick_sort(arr,k):\n",
    "            if k==0:\n",
    "                return \n",
    "            first = arr[0]\n",
    "            left,right = 0,len(arr) -1 \n",
    "            while(left<right):\n",
    "                while arr[right]>=first and left<right:\n",
    "                    right -=1\n",
    "                arr[left] = arr[right]\n",
    "                while arr[left]<first and left <right:\n",
    "                    left +=1\n",
    "                arr[right] = arr[left]\n",
    "            arr[left] = first\n",
    "            # print(arr,first,left,right)\n",
    "            if left ==k:\n",
    "                self.out.extend(arr[:left])\n",
    "                return \n",
    "            elif left == k -1 :\n",
    "                self.out.extend(arr[:left+1])\n",
    "                return\n",
    "            elif left >k:\n",
    "                quick_sort(arr[:left],k)\n",
    "            else:\n",
    "                self.out.extend(arr[:left+1])\n",
    "                quick_sort(arr[left+1:],k-left-1)\n",
    "\n",
    "        self.out = []\n",
    "        quick_sort(arr,k)\n",
    "        return self.out\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        ans = [-float(\"inf\")]*k\n",
    "        if k == 0:\n",
    "            return ans\n",
    "\n",
    "        for num in arr:\n",
    "            if -num > ans[0]:\n",
    "                heapq.heappushpop(ans, -num)\n",
    "\n",
    "        return [-num for num in ans]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:\n",
    "            return []\n",
    "\n",
    "        ans = [-float(\"inf\")]*k\n",
    "\n",
    "        for num in arr:\n",
    "            if -num > ans[0]:\n",
    "                heapq.heappushpop(ans, -num)\n",
    "\n",
    "        return [-num for num in ans]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:\n",
    "            return []\n",
    "        heap = [-x for x in arr[:k]]\n",
    "        heapq.heapify(heap)\n",
    "        for i in range(k,len(arr)):\n",
    "            if -heap[0] > arr[i]:\n",
    "                heapq.heappushpop(heap,-arr[i])\n",
    "        return [-x for x in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:\n",
    "            return []\n",
    "        \n",
    "        max_heap = []\n",
    "        \n",
    "        for num in arr:\n",
    "            if len(max_heap) < k:\n",
    "                heapq.heappush(max_heap, -num)\n",
    "            else:\n",
    "                if -num > max_heap[0]:\n",
    "                    heapq.heappop(max_heap)\n",
    "                    heapq.heappush(max_heap, -num)\n",
    "        \n",
    "        result = [-x for x in max_heap]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:return []\n",
    "        n = len(arr)\n",
    "        import random\n",
    "        def partition(l, r):\n",
    "            if l >= r: return\n",
    "            idx = random.randint(l, r)\n",
    "            arr[l], arr[idx] = arr[idx], arr[l]\n",
    "            p = l\n",
    "            p2 = r\n",
    "            while l < r:\n",
    "                while arr[r] > arr[p] and l < r:\n",
    "                    r -= 1\n",
    "                while arr[l] <= arr[p] and l < r:\n",
    "                    l += 1\n",
    "                if l < r: arr[l], arr[r] = arr[r], arr[l]\n",
    "            if l == r:\n",
    "                arr[p], arr[l] = arr[l], arr[p]\n",
    "        \n",
    "            partition(p, l - 1)\n",
    "            partition(l + 1, p2)\n",
    "        \n",
    "        partition(0, n - 1)\n",
    "        return arr[:k]\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        for num in arr:\n",
    "            heapq.heappush(ans, -num)\n",
    "            if len(ans) > k:\n",
    "                heapq.heappop(ans)\n",
    "        return [-num for num in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k==0:return []\n",
    "        res = []\n",
    "        for c in arr:\n",
    "            if len(res)<k:\n",
    "                heapq.heappush(res,-c)\n",
    "            else:\n",
    "                if -res[0]>c:\n",
    "                    heapq.heappop(res)\n",
    "                    heapq.heappush(res,-c)\n",
    "        return [-c for c in res]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        # 1.对原数组进行排序后取值\n",
    "        # new_arr = sorted(arr)\n",
    "        # return new_arr[0:k]\n",
    "        # 最小堆\n",
    "        if k == 0:\n",
    "            return []\n",
    "        \n",
    "        hq = []\n",
    "        for i in arr:\n",
    "            if len(hq) < k:\n",
    "                heapq.heappush(hq, -i)\n",
    "            else:\n",
    "                if hq[0] < -i:\n",
    "                    heapq.heappop(hq)\n",
    "                    heapq.heappush(hq, -i)\n",
    "        return [-i for i in hq]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        #print(arr)\n",
    "        #print(k)\n",
    "        if k==0:\n",
    "            return []\n",
    "        if k >= len(arr):\n",
    "            return arr\n",
    "        import heapq\n",
    "\n",
    "        l = [-arr[i] for i in range(k)]\n",
    "        #print(l)\n",
    "        heapq.heapify(l)\n",
    "        for i in range(k, len(arr)):\n",
    "            if -arr[i] > l[0]:\n",
    "                heapq.heappop(l)\n",
    "                heapq.heappush(l, -arr[i])\n",
    "        return [-i for i in l]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k==0:\n",
    "            return []\n",
    "        hp = [-x for x in arr[:k]]\n",
    "        heapq.heapify(hp)\n",
    "\n",
    "        for i in range(k,len(arr)):\n",
    "            if -hp[0] > arr[i]:\n",
    "                heapq.heappop(hp)\n",
    "                heapq.heappush(hp,-arr[i])\n",
    "        ans = [-x for x in hp]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k==0:\n",
    "            return []\n",
    "        hp = [-x for x in arr[:k]]\n",
    "        print(hp)\n",
    "        heapq.heapify(hp)\n",
    "        print(hp)\n",
    "        for x in arr[k:]:\n",
    "            if -x>hp[0]:\n",
    "                heapq.heappop(hp)\n",
    "                heapq.heappush(hp, -x)\n",
    "        res = [-x for x in hp][::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def heappush(stack,num):\n",
    "            n = len(stack)\n",
    "            stack.append(num)\n",
    "            father = (n-1) // 2\n",
    "            while n > 0 and father>=0 and stack[n] < stack[father]:\n",
    "                stack[n],stack[father] = stack[father],stack[n]\n",
    "                n = father\n",
    "                father = (n-1) // 2\n",
    "        def heappop(stack):\n",
    "            n = len(stack)\n",
    "            stack[0],stack[-1] = stack[-1],stack[0]\n",
    "            res = stack.pop()\n",
    "            root = -1\n",
    "            min_index =0\n",
    "            while root != min_index:\n",
    "                print(root,min_index)\n",
    "                root = min_index\n",
    "                left = root * 2 + 1\n",
    "                right = root * 2 + 2\n",
    "                if left < n-1 and stack[left] < stack[root]:\n",
    "                    min_index = left\n",
    "                if right < n - 1 and stack[right] <stack[min_index]:\n",
    "                    min_index = right\n",
    "                stack[root],stack[min_index] = stack[min_index],stack[root]\n",
    "            return res\n",
    "            \n",
    "        if k == 0:\n",
    "            return []\n",
    "        stack = []\n",
    "        for i,num in enumerate(arr):\n",
    "            if len(stack) < k:\n",
    "                heappush(stack,-num)\n",
    "                # print(stack)\n",
    "            elif -num > stack[0]:\n",
    "                heappop(stack)\n",
    "                heappush(stack,-num)\n",
    "        return [-i for i in stack]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        if n <= k: return arr\n",
    "        if k == 0: return []\n",
    "        ans = [-num for num in arr[:k]]\n",
    "        # print(ans)\n",
    "        heapq.heapify(ans)\n",
    "        print(ans)\n",
    "        for num in arr[k:]:\n",
    "            k = ans[0]\n",
    "            print(k)\n",
    "            if -num > k :\n",
    "                heapq.heappop(ans)\n",
    "                heapq.heappush(ans, -num)\n",
    "        return [-num for num in ans]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def select(arr, k):\n",
    "            if k == 0:\n",
    "                return []\n",
    "            mid = arr[0]\n",
    "            if len(arr) <= k:\n",
    "                return arr\n",
    "            left_arr = [i for i in arr[1:] if i <= mid]\n",
    "            if len(left_arr) == k:\n",
    "                return left_arr\n",
    "            elif len(left_arr) > k:\n",
    "                return select(left_arr, k)\n",
    "            else:\n",
    "                right_arr = [i for i in arr[1:] if i > mid]\n",
    "                return left_arr + [mid] + select(right_arr, k-len(left_arr)-1)\n",
    "        return select(arr, k)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        res = []\n",
    "        def helper(nums, k):\n",
    "            if not k: return\n",
    "            ind = random.randrange(len(nums))\n",
    "            nums[0], nums[ind] = nums[ind], nums[0]\n",
    "            smaller = [n for n in nums[1:] if n <= nums[0]]\n",
    "            larger = [n for n in nums[1:] if n > nums[0]]\n",
    "            if len(smaller) + 1 <= k:\n",
    "                res.extend(smaller + [nums[0]])\n",
    "                helper(larger, k - (len(smaller) + 1))\n",
    "            else:\n",
    "                helper(smaller, k)\n",
    "        helper(arr, k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections.abc\n",
    "visited = [False] \n",
    "def my_Assert(exp):\n",
    "    if exp:return\n",
    "    if not visited[0]:\n",
    "        visited[0]=1\n",
    "        assert(exp)\n",
    "def getcolor(node):\n",
    "    return not node or node.color\n",
    "\n",
    "def assert_legal(node):\n",
    "    if not node:return \n",
    "    if node.P: my_Assert(node.P.L == node or node.P.R == node)\n",
    "    if node.L: my_Assert(node.L.key < node.key)\n",
    "    if node.R: my_Assert(node.R.key > node.key)\n",
    "    my_Assert(node.color or (getcolor(node.P) and getcolor(node.L) and getcolor(node.R)))\n",
    "\n",
    "class TNode:\n",
    "    __slots__ = ('key','prev','next','L','R','P','color','__weakref__')\n",
    "\n",
    "    def __init__(self,key):\n",
    "        self.key = key\n",
    "        self.color = 0\n",
    "        self.L = None \n",
    "        self.R = None\n",
    "\n",
    "\n",
    "    def rotateR(self):\n",
    "        node = self.L\n",
    "        self.L = node.R \n",
    "        node.R = self\n",
    "\n",
    "        node.P = self.P \n",
    "        self.P = node \n",
    "        if self.L: self.L.P = self\n",
    "\n",
    "        node.color, self.color = self.color, node.color\n",
    "\n",
    "        return node\n",
    "        \n",
    "    \n",
    "    def rotateL(self):\n",
    "        node = self.R \n",
    "        self.R = node.L\n",
    "        node.L = self\n",
    "\n",
    "        node.P = self.P \n",
    "        self.P = node \n",
    "        if self.R: self.R.P = self\n",
    "\n",
    "        node.color, self.color = self.color, node.color\n",
    "\n",
    "        return node\n",
    "    \n",
    "\n",
    "    def match_parent(self):\n",
    "        if self.key<self.P.key:\n",
    "            self.P.L = self \n",
    "        elif self.key>self.P.key:\n",
    "            self.P.R = self\n",
    "\n",
    "    \n",
    "    def tree_setL(self, node):\n",
    "        node.chain_insert(self.prev,self)\n",
    "        node.P = self\n",
    "        self.L = node\n",
    "\n",
    "    \n",
    "    def tree_setR(self, node):\n",
    "        node.chain_insert(self,self.next)\n",
    "        node.P = self\n",
    "        self.R = node        \n",
    "\n",
    "\n",
    "    def chain_insert(self, prev, next):\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        prev.next = self\n",
    "        next.prev = self\n",
    "\n",
    "\n",
    "    def chain_remove(self):\n",
    "        p = self.prev\n",
    "        n = self.next\n",
    "        p.next = n \n",
    "        n.prev = p\n",
    "\n",
    "    def __repr__(self):\n",
    "        return [[self.L.key if self.L else None],self.key,[self.R.key if self.R else None]].__repr__()\n",
    "        \n",
    "\n",
    "class sorted_dict(dict):\n",
    "    \"\"\"\n",
    "    套用字典API的红黑树。\n",
    "    An RB-Tree with dict-like API.\n",
    "\n",
    "    直接继承dict的方法：\n",
    "    __contain__:    x in dict\n",
    "    __len__: len(dict)\n",
    "    \"\"\"\n",
    "\n",
    "    # init:\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        树的初始化：\n",
    "        dict() -> new empty Tree\n",
    "        \n",
    "        暂不允许其他形式的初始化。\n",
    "        dict(***any arguments) x-> not allowed\n",
    "        \"\"\"\n",
    "        super().__init__()\n",
    "        head = TNode(None)\n",
    "        self.__head = head.next = head.prev = head\n",
    "        self.__root = None\n",
    "        self.__map = {}\n",
    "        self.__stk = []\n",
    "        pass\n",
    "\n",
    "    # Function of Sorted_Dict\n",
    "    def _getnode(self,key):\n",
    "        return self.__map[key]\n",
    "    \n",
    "    def _getroot(self):\n",
    "        return self.__root\n",
    "\n",
    "    # Item getter/setter:\n",
    "    def __min__(self):\n",
    "        return self.__head.next.key\n",
    "\n",
    "    def __max__(self):\n",
    "        return self.__head.prev.key\n",
    "\n",
    "    def __setitem__(self,key,val):\n",
    "        if key not in self.__map:\n",
    "            new_node = TNode(key)\n",
    "            if not self.__map:\n",
    "                self.__root = root = new_node\n",
    "                root.P = None \n",
    "                root.color = 1\n",
    "                root.chain_insert(self.__head, self.__head)\n",
    "            else:\n",
    "\n",
    "                # 二叉树插入: O(logN)，确保效率\n",
    "                parent = self.__root\n",
    "                while(True):\n",
    "                    if key<parent.key:\n",
    "                        if parent.L:\n",
    "                            parent = parent.L\n",
    "                        else:\n",
    "                            parent.tree_setL(new_node)\n",
    "                            break\n",
    "                    else:\n",
    "                        if parent.R:\n",
    "                            parent = parent.R\n",
    "                        else:\n",
    "                            parent.tree_setR(new_node)\n",
    "                            break\n",
    "\n",
    "                #  旋转：O(1)，确保准确性\n",
    "                while(not parent.color):\n",
    "                    \n",
    "                    Grand = parent.P\n",
    "                     \n",
    "                    if not Grand:\n",
    "                        parent.color = 1\n",
    "                        break\n",
    "\n",
    "                    elif not Grand.L or Grand.L.color:\n",
    "                        # L = 1\n",
    "                        # R = parent = 0\n",
    "                        if not parent.R or parent.R.color:\n",
    "                            Grand.R = parent.rotateR()\n",
    "                        Grand = Grand.rotateL()\n",
    "                        if Grand.P:\n",
    "                            Grand.match_parent()\n",
    "                        else:\n",
    "                            self.__root = Grand\n",
    "                            Grand.P = None\n",
    "                        break\n",
    "                        \n",
    "                    elif not Grand.R or Grand.R.color:\n",
    "                        # L = parent = 0\n",
    "                        # R = 1\n",
    "                        if not parent.L or parent.L.color:\n",
    "                            Grand.L = parent.rotateL()\n",
    "                        Grand = Grand.rotateR()\n",
    "                        if Grand.P:\n",
    "                            Grand.match_parent()\n",
    "                        else:\n",
    "                            self.__root = Grand\n",
    "                            Grand.P = None\n",
    "                        break\n",
    "                        \n",
    "                    else:\n",
    "                        Grand.L.color = 1 \n",
    "                        Grand.R.color = 1\n",
    "                        parent = Grand.P\n",
    "                        if parent:\n",
    "                            Grand.color = 0\n",
    "                        else:\n",
    "                            break\n",
    "\n",
    "            self.__map[key] = new_node\n",
    "        super().__setitem__(key,val)\n",
    "\n",
    "    def __delitem__(self,key):\n",
    "        super().__delitem__(key)\n",
    "        # 确定节点\n",
    "        removednode = self.__map.pop(key)\n",
    "        if not removednode.L:\n",
    "            # 右孩子填充\n",
    "            parent = removednode.P\n",
    "            node = removednode.R\n",
    "        elif not removednode.R:\n",
    "            # 左孩子填充\n",
    "            parent = removednode.P\n",
    "            node = removednode.L\n",
    "        else:\n",
    "            # 与next互换后删除，其中next没有左节点\n",
    "            goatnode = removednode.next\n",
    "\n",
    "            goatnode.L = removednode.L \n",
    "            node = goatnode.R\n",
    "            if goatnode.P == removednode:\n",
    "                parent = goatnode\n",
    "                goatnode.R = None \n",
    "            else:\n",
    "                parent = goatnode.P\n",
    "                goatnode.R = removednode.R\n",
    "            goatnode.P = removednode.P \n",
    "            goatnode.color, removednode.color = removednode.color, goatnode.color\n",
    "            key = goatnode.key\n",
    "\n",
    "            goatnode.L.P = goatnode \n",
    "            if goatnode.R: goatnode.R.P = goatnode\n",
    "            if goatnode.P:\n",
    "                TNode.match_parent(goatnode)\n",
    "            else:\n",
    "                self.__root = goatnode\n",
    "            \n",
    "\n",
    "        # 删除：\n",
    "        TNode.chain_remove(removednode)\n",
    "        if node: \n",
    "            node.P = parent \n",
    "        if parent:\n",
    "            if key < parent.key:\n",
    "                parent.L = node\n",
    "            else:\n",
    "                parent.R = node  \n",
    "        else:\n",
    "            self.__root = node \n",
    "\n",
    "        # 旋转：\n",
    "        if not removednode.color or (node and not node.color):\n",
    "            # 情况0：删除节点或其子节点是红色的：将子节点与父节点相连，子节点涂黑，无需旋转\n",
    "            # 等价于B(4)树删除了3节点的元素\n",
    "            if node: \n",
    "                node.color = 1\n",
    "            return\n",
    "\n",
    "\n",
    "        while(parent):\n",
    "            if key < parent.key:\n",
    "                # 兄弟在右：\n",
    "                brother = parent.R\n",
    "                if brother and not brother.color:\n",
    "                    # 情况2：兄弟节点为红色：父节点左旋，转为兄弟节点为黑色的情形。\n",
    "                    grand = TNode.rotateL(parent)\n",
    "                    if grand.P:\n",
    "                        TNode.match_parent(grand)\n",
    "                    else:\n",
    "                        self.__root = grand\n",
    "                    brother = parent.R\n",
    "\n",
    "                if brother and brother.L and not brother.L.color:\n",
    "                    # 情况3：兄弟的内侧(L)子节点为红色：兄弟节点右旋，转为兄弟的外侧节点为红色的情形。\n",
    "                    parent.R = brother = TNode.rotateR(brother)\n",
    "                \n",
    "                if brother and brother.R and not brother.R.color:\n",
    "                    # 情况4：兄弟的外侧(R)子节点为红色：将该节点涂黑，父节点左旋，恢复平衡。\n",
    "                    brother.R.color = 1\n",
    "                    grand = TNode.rotateL(parent)\n",
    "                    if grand.P:\n",
    "                        TNode.match_parent(grand)\n",
    "                    else:\n",
    "                        self.__root = grand\n",
    "                    return\n",
    "            \n",
    "\n",
    "            else:\n",
    "                # 兄弟在左：\n",
    "                brother = parent.L\n",
    "                if brother and not brother.color:\n",
    "                    # 情况2：兄弟节点为红色：父节点右旋，转为兄弟节点为黑色的情形。\n",
    "                    grand = TNode.rotateR(parent)\n",
    "                    if grand.P:\n",
    "                        TNode.match_parent(grand)\n",
    "                    else:\n",
    "                        self.__root = grand\n",
    "                    brother = parent.L\n",
    "                if brother and brother.R and not brother.R.color:\n",
    "                    # 情况3：兄弟的内侧(R)子节点为红色：兄弟节点左旋，转为兄弟的外侧节点为红色的情形。\n",
    "                    parent.L = brother = TNode.rotateL(brother)\n",
    "                \n",
    "                if brother and brother.L and not brother.L.color:\n",
    "                    # 情况4：兄弟的外侧(L)子节点为红色：将该节点涂黑，父节点右旋，恢复平衡。\n",
    "                    brother.L.color = 1\n",
    "                    grand = TNode.rotateR(parent)\n",
    "                    if grand.P:\n",
    "                        TNode.match_parent(grand)\n",
    "                    else:\n",
    "                        self.__root = grand\n",
    "                    break\n",
    "\n",
    "            if not parent.color:\n",
    "                # 情况5：兄弟节点及其子节点全黑，但父节点是红色：兄弟和父节点颜色互换，恢复平衡。\n",
    "                if brother:\n",
    "                    parent.color = 1\n",
    "                    brother.color = 0\n",
    "                else:\n",
    "                    parent.color = 0\n",
    "                break \n",
    "\n",
    "            else:\n",
    "                # 情况6：父节点也是黑的：将兄弟节点涂红，在父节点上递归。\n",
    "                brother.color = 0\n",
    "                node = parent\n",
    "                key = node.key\n",
    "                parent = parent.P\n",
    "\n",
    "\n",
    "        else:\n",
    "            # 情况1：递归到根，无需旋转\n",
    "            self.__root = node \n",
    "            if node:\n",
    "                node.color = 1\n",
    "            return \n",
    "\n",
    "    \n",
    "    def pop(self, key):\n",
    "        res = self[key]\n",
    "        self.__delitem__(key)\n",
    "        return res\n",
    "\n",
    "    def popitem(self):\n",
    "        pass\n",
    "    \n",
    "    def setdefault(self, key, default = None):\n",
    "        pass\n",
    "\n",
    "    # Iterator:\n",
    "    def __iter__(self):\n",
    "        head = self.__head\n",
    "        cur = head.next\n",
    "        while(cur is not head):\n",
    "            yield cur.key\n",
    "            cur = cur.next\n",
    "\n",
    "\n",
    "    def __reversed__(self):\n",
    "        head = self.__head\n",
    "        cur = head.prev\n",
    "        while(cur is not head):\n",
    "            yield cur.key\n",
    "            cur = cur.prev\n",
    "        \n",
    "    def keys(self):\n",
    "        return collections.abc.KeysView(self)\n",
    "\n",
    "    def values(self):\n",
    "        return collections.abc.ValuesView(self)\n",
    "\n",
    "    def items(self):\n",
    "        return collections.abc.ItemsView(self)\n",
    "\n",
    "    # Dict Operations:\n",
    "    def clear(self):\n",
    "        pass\n",
    "\n",
    "    def copy(self):\n",
    "        pass\n",
    "\n",
    "    def update(self, others):\n",
    "        pass\n",
    "\n",
    "    def fromkeys(self, it, val):\n",
    "        pass\n",
    "\n",
    "    # Str Expressions:\n",
    "    # def __str__(self):\n",
    "    #     pass\n",
    "\n",
    "    # def __repr__(self):\n",
    "    #     pass\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        # return sorted(arr)[:k]\n",
    "        dic = sorted_dict()\n",
    "        for i in arr[:k]:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        for i in arr[k:]:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else:\n",
    "                dic[i]=1\n",
    "            k = dic.__max__()\n",
    "            if dic[k]==1:\n",
    "                dic.pop(k)\n",
    "            else:\n",
    "                dic[k]-=1\n",
    "        res = []\n",
    "        for i in dic:\n",
    "            res += [i]*dic[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        num=collections.Counter(arr)\n",
    "        num=[(i[0],i[1]) for i in num.items()]\n",
    "        heap=[]\n",
    "        for n in num:\n",
    "            heapq.heappush(heap,n) ## 大顶推\n",
    "        print(heap)\n",
    "        re=[]\n",
    "        while k>0:\n",
    "            col=heapq.heappop(heap) ##\n",
    "            # cot=heapq.heappop(heap)\n",
    "            if k>col[1]:\n",
    "                k-=col[1]\n",
    "                # re.attend(col)\n",
    "                re+=[col[0]]*col[1]\n",
    "            else:\n",
    "                re+=[col[0]]*k\n",
    "                break\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k > len(arr) or k == 0:\n",
    "            return []\n",
    "        index = randint(0,len(arr)-1)\n",
    "        pivot = arr[index]\n",
    "        small=[i for i in (arr[:index]+arr[index+1:])if i < pivot]\n",
    "        large=[i for i in (arr[:index]+arr[index+1:])if i >= pivot]\n",
    "\n",
    "        if k-1 == len(small):\n",
    "            return small + [pivot]\n",
    "        elif k-1<len(small):\n",
    "            return self.smallestK(small,k)\n",
    "        if k-1 > len(small):\n",
    "                return small + self.smallestK(large,k-len(small)-1) + [pivot]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def quickSort(arr,L):\n",
    "            if L ==0:\n",
    "                return []\n",
    "            # print(arr,L)\n",
    "            if arr == []:\n",
    "                return []\n",
    "            pivot = arr[0]\n",
    "            left = []\n",
    "            right = []\n",
    "            for i in range(1,len(arr)):\n",
    "                if arr[i]<=pivot:\n",
    "                    left.append(arr[i])\n",
    "                else:\n",
    "                    right.append(arr[i])\n",
    "            if len(left) == 0:\n",
    "                return [pivot] + quickSort(right,L-1)\n",
    "            elif len(left)<L-1:\n",
    "                # print('here')\n",
    "                return left+[pivot]+quickSort(right,L-len(left)-1)\n",
    "            elif len(left) == L-1:\n",
    "                return left+[pivot]\n",
    "            elif len(left) == L:\n",
    "                return left\n",
    "            else:\n",
    "                return quickSort(left,L)\n",
    "        return quickSort(arr,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if(len(arr) <= k):\n",
    "            return arr \n",
    "        target = arr[0]\n",
    "        left, mid, right = [], [], []\n",
    "        for a in arr:\n",
    "            if(a < target):\n",
    "                left.append(a)\n",
    "            elif(a > target):\n",
    "                right.append(a)\n",
    "            else:\n",
    "                mid.append(a)\n",
    "        if(len(left) >= k):\n",
    "            return self.smallestK(left,k)\n",
    "        else:\n",
    "            if(len(left) + len(mid) >= k):\n",
    "                return left + mid[:k-len(left)]\n",
    "            else:\n",
    "                return left + mid + self.smallestK(right,k-len(left)-len(mid))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        return heapq.nlargest(k,arr,key=lambda x:-x)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        queue = PriorityQueue()\n",
    "        for i, num in enumerate(arr):\n",
    "            queue.put((num, num))\n",
    "        res = []\n",
    "        while k>0:\n",
    "            res.append(queue.get()[0])\n",
    "            k-=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  \n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:  \n",
    "        def sortq(xx):  \n",
    "            if len(xx) <= 1:  \n",
    "                return xx  \n",
    "            pivot = xx[len(xx) // 2]  # 选取基准值  \n",
    "            left = [x for x in xx if x < pivot]  \n",
    "            mid = [x for x in xx if x == pivot]  \n",
    "            right = [x for x in xx if x > pivot]  \n",
    "            return sortq(left) + mid + sortq(right)  \n",
    "        xxx = sortq(arr)  \n",
    "        return xxx[:k]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def quickSort(arr,L):\n",
    "            if L ==0:\n",
    "                return []\n",
    "            if arr == []:\n",
    "                return []\n",
    "            pivot = arr[0]\n",
    "            left = []\n",
    "            right = []\n",
    "            for i in range(1,len(arr)):\n",
    "                if arr[i]<=pivot:\n",
    "                    left.append(arr[i])\n",
    "                else:\n",
    "                    right.append(arr[i])\n",
    "            if len(left) == 0:\n",
    "                return [pivot] + quickSort(right,L-1)\n",
    "            elif len(left)<L-1:\n",
    "                # print('here')\n",
    "                return left+[pivot]+quickSort(right,L-len(left)-1)\n",
    "            elif len(left) == L-1:\n",
    "                return left+[pivot]\n",
    "            elif len(left) == L:\n",
    "                return left\n",
    "            else:\n",
    "                return quickSort(left,L)\n",
    "        return quickSort(arr,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if not arr:\n",
    "            return arr\n",
    "        left = []\n",
    "        left_counter = 0\n",
    "        right = []\n",
    "        right_counter = 0\n",
    "        pivot = arr[0]\n",
    "        for i in arr[1:]:\n",
    "            if i < pivot:\n",
    "                left.append(i)\n",
    "                left_counter += 1\n",
    "            else:\n",
    "                right.append(i)\n",
    "                right_counter += 1\n",
    "        if left_counter + 1 == k:\n",
    "            return left + [pivot]\n",
    "        elif left_counter + 1 < k:\n",
    "            return left + [pivot] + self.smallestK(right, k - left_counter - 1)\n",
    "        else:\n",
    "            return self.smallestK(left, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        def partition(arr):\n",
    "            cnt, pivot = 0, arr[0]\n",
    "            left, right = [], []\n",
    "            for num in arr[1:]:\n",
    "                if num < pivot:\n",
    "                    left.append(num)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    right.append(num)\n",
    "            return left, pivot, right, cnt\n",
    "\n",
    "        def select_ksmallest(arr, k):\n",
    "            if not arr:\n",
    "                return []\n",
    "            left, pivot, right, cnt = partition(arr)\n",
    "            if cnt == k:\n",
    "                return left\n",
    "            elif cnt > k:\n",
    "                return select_ksmallest(left, k)\n",
    "            else:\n",
    "                return left + [pivot] + select_ksmallest(right, k - cnt - 1)\n",
    "\n",
    "        return select_ksmallest(arr, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        # return sorted(arr)[0:k]\n",
    "        if k>=len(arr):\n",
    "            return arr\n",
    "        # if k==0:return []\n",
    "        # print(arr)\n",
    "        a=arr[0]\n",
    "        left, right = [],[]\n",
    "        for x in arr[1:]:\n",
    "            if x<a:\n",
    "                left.append(x)\n",
    "            else:\n",
    "                right.append(x)\n",
    "        # print(left, right)\n",
    "        if len(left)+1==k:\n",
    "            return left+[a]\n",
    "        elif len(left)+1>k:\n",
    "            return self.smallestK(left,k)\n",
    "        else:\n",
    "            return left+[a]+self.smallestK(right,k-len(left)-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if len(arr) == k:\n",
    "            return arr\n",
    "        left, right = [], []\n",
    "        for item in arr[1:]:\n",
    "            if item < arr[0]:\n",
    "                left.append(item)\n",
    "            else:\n",
    "                right.append(item)\n",
    "        if len(left) < k - 1:\n",
    "            return left + [arr[0]] + self.smallestK(right, k - len(left) - 1)\n",
    "        elif len(left) == k - 1:\n",
    "            return left + [arr[0]]\n",
    "        elif len(left) == k:\n",
    "            return left\n",
    "        else:\n",
    "            return self.smallestK(left, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        # heap_l=heapify(arr)\n",
    "        # print(heapq.nsmallest(k,arr))\n",
    "        return list(heapq.nsmallest(k,arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  \n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:  \n",
    "        def sortq(xx):  \n",
    "            if len(xx) <= 1:  \n",
    "                return xx  \n",
    "            pivot = xx[0]  # 选取基准值  \n",
    "            left = [x for x in xx if x < pivot]  \n",
    "            mid = [x for x in xx if x == pivot]  \n",
    "            right = [x for x in xx if x > pivot]  \n",
    "            return sortq(left) + mid + sortq(right)  \n",
    "        xxx = sortq(arr)  \n",
    "        return xxx[:k]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        heap = []\n",
    "        arr = [-x for x in arr]\n",
    "        if k == 0:\n",
    "            return []\n",
    "        for num in arr:\n",
    "            if len(heap) < k:\n",
    "                heapq.heappush(heap, num)\n",
    "            else:\n",
    "                if heap[0] < num: #-8 < -4\n",
    "                    heapq.heappop(heap)\n",
    "                    heapq.heappush(heap, num)\n",
    "                else:\n",
    "                    continue\n",
    "        return [-x for x in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k==0:\n",
    "            return []\n",
    "        import heapq\n",
    "        hp=[-x for x in arr]\n",
    "        heapq.heapify(hp)\n",
    "        tg=hp[0:k]\n",
    "        for i in range(k,len(arr)):\n",
    "            \n",
    "            if tg[0] < hp[i]:\n",
    "                heapq.heappop(tg)\n",
    "                heapq.heappush(tg,hp[i])\n",
    "        return [-x for x in tg]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:\n",
    "            return []\n",
    "        if len(arr) == 0:\n",
    "            return []\n",
    "        pivot = arr[0]\n",
    "        i = 0\n",
    "        j = len(arr)\n",
    "        while i + 1 < j:\n",
    "            if arr[i + 1] < pivot:\n",
    "                i = i + 1\n",
    "            else:\n",
    "                j = j - 1\n",
    "                tmp = arr[i+1]\n",
    "                arr[i+1] = arr[j]\n",
    "                arr[j] = tmp\n",
    "        if i != 0:\n",
    "            tmp = arr[i]\n",
    "            arr[i] = pivot\n",
    "            arr[0] = tmp\n",
    "        if i == k - 1:\n",
    "            return arr[:k]\n",
    "        elif i > k - 1:\n",
    "            return self.smallestK(arr[:i], k)\n",
    "        return arr[:i + 1] + self.smallestK(arr[i + 1:], k - 1 - i)\n",
    "        \n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "# 使用python3内置小根堆\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k <= 0:\n",
    "            return []\n",
    "        elif not arr or len(arr) <= k:\n",
    "            return arr\n",
    "        A = [-x for x in arr]\n",
    "        hp_list = A[:k]\n",
    "        heapq.heapify(hp_list)\n",
    "        for x in A[k:]:\n",
    "            if x > hp_list[0]:\n",
    "                heapq.heappushpop(hp_list, x)\n",
    "        return [-x for x in hp_list]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        arr = [-x for x in arr]\n",
    "        if k == 0:\n",
    "            return []\n",
    "        for num in arr:\n",
    "            if len(ans) < k:\n",
    "                heapq.heappush(ans, num)\n",
    "            else:\n",
    "                if ans[0] < num:\n",
    "                    heapq.heappop(ans)\n",
    "                    heapq.heappush(ans, num)\n",
    "                else:\n",
    "                    continue\n",
    "        return [-x for x in ans]\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        # return sorted(arr)[:k]\n",
    "        return nsmallest(k, arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        if k == 0:\n",
    "            return []\n",
    "        \n",
    "        nums = [-v for v in arr]\n",
    "        hp = []\n",
    "        for i in range(k):\n",
    "            heapq.heappush(hp, nums[i])\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            if hp[0] < nums[i]:\n",
    "                heapq.heapreplace(hp, nums[i])\n",
    "        return [-v for v in hp]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestK(self, arr: List[int], k: int) -> List[int]:\n",
    "        reverse_arr = [-n for n in arr]\n",
    "        heap = []\n",
    "        for num in reverse_arr:\n",
    "            if len(heap) < k:\n",
    "                heapq.heappush(heap, num)\n",
    "            else:\n",
    "                heapq.heappushpop(heap, num)\n",
    "        result = [-n for n in heapq.nlargest(k, heap)]\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
